/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann Tübingen, Germany 
 * Niko Schenk Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package collectors.impl.visitors;

import util.Interval;
import collectors.api.PreOrderCollector;
import saphre.core.Store;
import saphre.core.SuffixArray;

/**
 * A class that serves as the basis for several programs in the 'examples'
 * directory. Provides a kind of callback approach, so the programmer only needs
 * to be concerned with what information is to be gathered during the traversal,
 * and can ignore the mechanics of the traversal itself.
 * 
 * @author Dale Gerdemann
 */
public class InOrderTraversal {

    Store store;
    SuffixArray sa;
    PreOrderCollector collect;
    Interval top;
    SuffixArray pa;
    // The following is used to show lcp-interval tree as in fig 7 of
    // Kim et al. See PrintTraversal2.java.
    public static int lcpStart = 0;

    /**
     * 
     * @param store
     * @param sa
     * @param collect
     * @param top 
     */
    public InOrderTraversal(Store store, SuffixArray sa,
            PreOrderCollector collect, Interval top) {
        this.store = store;
        this.sa = sa;
        this.collect = collect;
        this.top = top;
    }

    /**
     * 
     */
    public void traverse() {
        traverse(top, lcpStart, 0);
    }

    /*
     * 
     */
    private void traverse(Interval inter, int lcp, int depth) {
        if (inter.trivial()) {
            collect.addTrivial(inter, lcp, depth);
        } else {
            int mid = sa.cldtab[inter.lb()];
            if (mid <= inter.lb() || mid > inter.rb()) {
                mid = sa.cldtab[inter.rb()];
            }
            Interval left = new Interval(inter.lb(), mid - 1);
            Interval right = new Interval(mid, inter.rb());
            // boolean lcpInter = false;
            int parentLcp = lcp;
            boolean proceed = true;
            int indent = 0;
            traverse(left, lcp, depth + indent);
            if (lcp < sa.lcptab[mid]) {
                lcp = sa.lcptab[mid];
                proceed = collect.add(inter, parentLcp, lcp, depth);
                indent = 1;
            }
            traverse(right, lcp, depth + indent);
        }
    }
}
